#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "32.h"

static void llist_sym_free(struct llist_sym *);
static void llist_rul_free(struct llist_rul *);
static int set_add_not_e(set, set);
static int get_index(symbol[], symbol, int);
static int ruleset_contains(ruleset, rule);
static int rulcmp(rule, rule);
static void print_ruleset(ruleset, FILE *, symbol);
static void print_rule(rule, FILE *);

/*!
*
* calculate the first sets for the given grammar
*
* \param[in] nonterminals array of nonterminal tokens
* \param[in] num_nonterm number of nonterminal tokens
* \param[in] rules array of production rules
* \param[in] num_rules number of production rules
* \param[out] firsts first sets for each nonterminal
*
*/
void build_first_sets(symbol nonterminals[], int num_nonterm,
                      rule rules[], int num_rules, set firsts[])
{
  register int changed = 1;
  register int i;
  for (i = 0; i < num_nonterm; i++)
    EMPTY_SET(firsts[i]);
  while (changed)
  {
    for (i = 0; i < num_rules; i++)
    {
      register int j;
      register int cont = 1;
      int nonterm = get_index(nonterminals, rules[i]->nonterm, num_nonterm);
      for (j = 0; (j < rules[i]->num_components) && cont; j++)
      {
        symbol s = rules[i]->components[j];
        int index = get_index(nonterminals, s, num_nonterm);
        if (index < 0)
        {
          changed = set_add(firsts[nonterm], s);
          cont = 0;
        }
        else
        {
          set s = firsts[index];
          changed = set_add_not_e(firsts[nonterm], s) || changed;
          if (! set_contains(s, EPSILON))
            cont = 0;
        }
      }
      if (cont)
        changed = set_add(firsts[nonterm], EPSILON) || changed;
    }
  }
}

/*!
*
* calculate the follow sets for the given grammar
*
* \param[in] nonterminals array of nonterminal tokens (Start symbol first)
* \param[in] num_nonterm number of nonterminal tokens
* \param[in] rules array of production rules
* \param[in] num_rules number of production rules
* \param[in] firsts first sets for each nonterminal
* \param[out] follows follow sets for each nonterminal
*
*/
void build_follow_sets(symbol nonterminals[], int num_nonterm, rule rules[],
                       int num_rules, const set firsts[], set follows[])
{
  register int changed = 1;
  register int i;
  for (i = 0; i < num_nonterm; i++)
    EMPTY_SET(follows[i]);
  set_add(follows[0], "$");
  while (changed)
  {
    changed = 0;
    for (i = 0; i < num_rules; i++)
    {
      register int j;
      for (j = 0; j < rules[i]->num_components; j++)
      {
        int index = get_index(nonterminals,
                              rules[i]->components[j], num_nonterm);
        if (index >= 0)
        {
          register int k;
          int epsilon = 1;
          for (k = j+1; k < rules[i]->num_components; k++)
          {
            int indexk = get_index(nonterminals,
                                   rules[i]->components[k], num_nonterm);
            if (indexk < 0)
            {
              changed = set_add(follows[index], rules[i]->components[k])
                        || changed;
              if (! IS_EPSILON(rules[i]->components[k]))
              {
                epsilon = 0;
                break;
              }
            }
            else
            {
              changed = set_add_not_e(follows[index], firsts[indexk])
                        || changed;
              if(! set_contains(firsts[indexk], EPSILON))
              {
                epsilon = 0;
                break;
              }
            }
          }
          if (epsilon)
          {
            int e = get_index(nonterminals, rules[i]->nonterm, num_nonterm);
            changed = set_add_not_e(follows[index], follows[e]) || changed;
          }
        }
      }
    }
  }
}

/*!
*
* calculate the parsing table for the given grammar
*
* \param[in] tokens array of tokens
* \param[in] num_tokens number of tokens
* \param[in] nonterminals array of nonterminal tokens
* \param[in] num_nonterm number of nonterminal tokens
* \param[in] rules array of production rules
* \param[in] num_rules number of production rules
* \param[in] firsts first sets for each nonterminal
* \param[in] follows follow sets for each nonterminal
* \param[out] table parsing table; array of size [num_nonterms][num_tokens]
*
*/
void build_table(symbol tokens[], int num_tokens, symbol nonterminals[],
                 int num_nonterms, const rule rules[], int num_rules,
                 const set firsts[], const set follows[], ruleset * table)
{
  register int i;
  for (i = 0; i < num_nonterms; i++)
  {
    register int j;
    for (j = 0; j < num_tokens; j++)
      EMPTY_RULESET(table[i*num_tokens+j]);
  }
  for (i = 0; i < num_rules; i++)
  {
    register int j;
    const int nonterm = get_index(nonterminals, rules[i]->nonterm, num_nonterms);
    ruleset * const rset = &table[nonterm*num_tokens];
    register int epsilon = 1;
    for (j = 0; j < rules[i]->num_components; j++)
    {
      int token = get_index(tokens, rules[i]->components[j], num_tokens);
      if (get_index(nonterminals, rules[i]->components[j], num_nonterms) < 0)
      {
        ruleset_add(rset[token], rules[i]);
        epsilon = 0;
        break;
      }
      else
      {
        register struct llist_sym * l = *firsts[nonterm];
        while (l)
        {
          int token = get_index(tokens, l->value, num_tokens);
          ruleset_add(rset[token], rules[i]);
          l = l->next;
        }
        if (! set_contains(firsts[nonterm], EPSILON))
        {
          epsilon = 0;
          break;
        }
      }
    }
    if (epsilon)
    {
      register struct llist_sym * l = *follows[nonterm];
      while (l)
      {
        int token = get_index(tokens, l->value, num_tokens);
        ruleset_add(rset[token], rules[i]);
        l = l->next;
      }
    }
  }
}

/*!
*
* print the parsing table to a file
*
* \param[in] table parsing table; array of size [nonterms][tokens]
* \param[in] nonterms number of nonterminal tokens
* \param[in] ntokens number of tokens
* \param[in] tokens array of tokens
* \param[out] out output file
*
*/
void print_table(const ruleset * table, int nonterms,
                 int ntokens, symbol tokens[], FILE * out)
{
  register int i;
  register const ruleset * row = table;
  for (i = 0; i < nonterms; i++)
  {
    register int j;
    for (j = 0; j < ntokens; j++)
    {
      print_ruleset(row[j], out, tokens[j]);
      fprintf(out, "\n");
    }
    fprintf(out, "---------=========---------\n");
    row += ntokens;
  }
}

int set_add_not_e(set out, set in)
{
  register struct llist_sym * i = *in;
  int ret = 0;
  while (i)
  {
    if (! IS_EPSILON(i->value))
      ret = set_add(out, i->value) || ret;
    i = i->next;
  }
  return ret;
}

int set_add(set out, symbol in)
{
  if (set_contains(out, in))
    return 0;
  else
  {
    register struct llist_sym * o = malloc(sizeof(*o));
    if (! o)
      exit(EXIT_FAILURE);
    else
    {
      o->value = in;
      o->next = NULL;
      if (*out)
      {
        struct llist_sym * ou = *out;
        while (ou->next)
          ou = ou->next;
        ou->next = o;
      }
      else
        *out = o; 
    }
    return 1;
  }
}

int ruleset_add(ruleset out, rule in)
{
  if (ruleset_contains(out, in))
    return 0;
  else
  {
    register struct llist_rul * o = malloc(sizeof(*o));
    if (! o)
      exit(EXIT_FAILURE);
    else
    {
      o->r = in;
      o->next = NULL;
      if (*out)
      {
        struct llist_rul * ou = *out;
        while (ou->next)
          ou = ou->next;
        ou->next = o;
      }
      else
        *out = o; 
    }
    return 1;
  }
}

int set_contains(set s, symbol e)
{
  register struct llist_sym * l = *s;
  while (l)
  {
    if (! strcmp(l->value,e))
      return 1;
    l = l->next;
  }
  return 0;
}

int ruleset_contains(ruleset s, rule e)
{
  register struct llist_rul * l = *s;
  while (l)
  {
    if (! rulcmp(l->r,e))
      return 1;
    l = l->next;
  }
  return 0;
}

int get_index(symbol ss[], symbol s, int len)
{
  register int i;
  for (i = 0; i < len; i++)
    if (! strcmp(ss[i], s))
      return i;
  return -1;
}

void empty_set(set * s)
{
  *s = malloc(sizeof(**s));
  if (! *s)
    exit(EXIT_FAILURE);
  else
    **s = NULL;
}

void empty_ruleset(ruleset * s)
{
  *s = malloc(sizeof(**s));
  if (! *s)
    exit(EXIT_FAILURE);
  else
    **s = NULL;
}

void set_free(set * s)
{
  llist_sym_free(**s);
  free(*s);
  *s = NULL;
}

void ruleset_free(ruleset * s)
{
  llist_rul_free(**s);
  free(*s);
  *s = NULL;
}

void llist_sym_free(struct llist_sym * l)
{
  if (l->next)
    llist_sym_free(l->next);
  free(l);
}

void llist_rul_free(struct llist_rul * l)
{
  if (l->next)
    llist_rul_free(l->next);
  free(l);
}

int rulcmp(rule a, rule b)
{
  register int cmp = strcmp(a->nonterm, b->nonterm);
  if (! cmp)
    cmp = a->num_components - b->num_components;
  if (! cmp)
  {
    register int i;
    for (i = 0; i < a->num_components; i++)
      if ((cmp = strcmp(a->components[i], b->components[i])))
        break;
  }
  return cmp;
}

void print_ruleset(ruleset rs, FILE * out, symbol token)
{
  register struct llist_rul * l = *rs;
  while (l)
  {
    fprintf(out, "%s ==> ", token);
    print_rule(l->r, out);
    fprintf(out, ":: ");
    l = l->next;
  }
}

void print_rule(rule r, FILE * out)
{
  register int i;
  fprintf(out, "%s >>", r->nonterm);
  for (i = 0; i < r->num_components; i++)
    fprintf(out, " %s", r->components[i]);
}

void print_set(set s, FILE * out)
{
  register struct llist_sym * l = *s;
  while (l)
  {
    fprintf(out, "\t%s\n", l->value);
    l = l->next;
  }
}

int set_size(set s)
{
  register int size = 0;
  register struct llist_sym * l = *s;
  while (l)
  {
    size++;
    l = l->next;
  }
  return size;
}

int ruleset_size(ruleset s)
{
  register int size = 0;
  register struct llist_rul * l = *s;
  while (l)
  {
    size++;
    l = l->next;
  }
  return size;
}
